class Solution{
public:
  int maxProfit(vector<int> &prices){

    int n = prices.size();
    int min[n + 3];
    int dp[n + 3];
    if(prices.size() != 0){
      memset(dp, 0, sizeof(dp));
      memset(min, 0, sizeof(min));

      min[0] = prices[0];
      for(int i = 1; i < n; ++i){
        min[i] = std::min(prices[i], min[i - 1]);
      }

      for(int i = 0; i < n; ++i){
        dp[i + 1] = max(prices[i] - min[i], dp[i]);
      }
    }
    return dp[n];

  }
};